package com.lun.medium;

import com.lun.util.BinaryTree.TreeNode;

public class ConstructBinarySearchTreeFromPreorderTraversal {
	
	//方法一：自己写的
    public TreeNode bstFromPreorder(int[] preorder) {
        return bstFromPreorder(preorder, 0, preorder.length - 1);
    }
    
    private TreeNode bstFromPreorder(int[] preorder, int start, int end) {
    	if(start > end) return null;
    	
    	TreeNode parent = new TreeNode(preorder[start]);
    	
    	//binary search
    	int boundary = start;
    	int left = boundary + 1, right = end; 
    	
    	while(left <= right) {
    		int mid = left + (right - left) / 2;
    		if(preorder[mid] < parent.val) {
    			if(mid + 1 > end || preorder[mid + 1] > parent.val) {
    				boundary = mid;
    				break;
    			}
    			left = mid + 1;
    		}else {
    			right = mid - 1;
    		}
    	}
    	
    	parent.left = bstFromPreorder(preorder, start + 1, boundary);
    	parent.right = bstFromPreorder(preorder, boundary + 1, end);
    	
    	return parent;
    }
    

    //方法二：别人写的1
    public TreeNode bstFromPreorder2(int[] preorder) { 
    	TreeNode root = null;
    	for(int val : preorder) 
    		root = insert(root, val);
    	return root;
    }
    
    private TreeNode insert(TreeNode root, int val) {
    	
    	if(root == null) 
    		return new TreeNode(val);
    	else if(root.val > val) 
    		root.left = insert(root.left, val);
    	else 
    		root.right = insert(root.right, val);
    	return root;
    }
    
    
    //方法三：别人写的2
    public TreeNode bstFromPreorder3(int[] A) {
        return bstFromPreorder(A, Integer.MAX_VALUE, new int[]{0});
    }

    public TreeNode bstFromPreorder(int[] A, int bound, int[] i) {
        if (i[0] == A.length || A[i[0]] > bound) return null;
        TreeNode root = new TreeNode(A[i[0]++]);
        root.left = bstFromPreorder(A, root.val, i);
        root.right = bstFromPreorder(A, bound, i);
        return root;
    }
    
}
